package com.mango.leet.code.middle;

/**
 * 剑指 Offer 56 - I. 数组中数字出现的次数
 */
/**
 * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [4,1,4,6]
 * 输出：[1,6] 或 [6,1]
 * 示例 2：
 *
 * 输入：nums = [1,2,10,4,1,4,3,3]
 * 输出：[2,10] 或 [10,2]
 *  
 *
 * 限制：
 *
 * 2 <= nums.length <= 10000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.Arrays;

/**
 * @Author: mango
 * @Date: 2022/3/24 9:49 下午
 */
public class LCoffer_56 {
    public static void main(String[] args) {
        //int[] nums = {1,2,2,3,3,4};
        int[] nums = {1,2,10,4,1,4,3,3};
        //int[] nums = {4,1,4,6};
        System.out.println(Arrays.toString(new Solution().singleNumbers(nums)));
        //System.out.println(1^7);
        System.out.println("5 rightOne="+rightOne(5));
        System.out.println("8 rightOne="+rightOne(8));
        System.out.println("12 rightOne="+rightOne(12));
    }

    public static int rightOne(int num){
        // 原码 & 补码（取反加一）
        return num & (~num + 1);
    }
    static class Solution {
        // 异或运算(相同为0，不同为1) a ^ a = 0 ; a ^ 0 = a;
        public int[] singleNumbers(int[] nums) {
            // 找出 eor = a ^ b
            int eor = 0;
            for(int i=0;i<nums.length;i++){
                eor ^= nums[i];
            }
            //System.out.println("eor="+eor);
            // 得到最右边为1的数字
            int m = eor & (~eor +1);
            //System.out.println("m="+m);
            int a = 0, b = 0;
            for(int i=0;i<nums.length;i++){
                // 与1 为0的一组做异或
                if((nums[i] & m) == 0){
                    a ^= nums[i];
                }else{
                    // 与1 不为0的一组组异或
                    b ^= nums[i];
                }
            }
            return new int[]{a,b};
        }
    }
}
